#include<iostream>
#include<stack>

using namespace std;

struct BinaryTreeNode {
	int value;
	BinaryTreeNode * left;
	BinaryTreeNode * right;
};

BinaryTreeNode * CreateBinaryTreeNode(int value){
    BinaryTreeNode * pHead = new BinaryTreeNode();
    pHead->value = value;
    pHead -> left = pHead -> right = nullptr;
    return pHead;
}

// connect ListNode
void ConnectTreeNodes( BinaryTreeNode * root , 
					BinaryTreeNode * left, BinaryTreeNode * right){
    root -> left = left;
	root -> right = right;
}



// 递归实现
void mirrorOfBinaryTree(BinaryTreeNode * root){
	if ( root != nullptr && ( root->left != nullptr || root->right!=nullptr ) ){
		if ( root -> left != nullptr ){
			mirrorOfBinaryTree(root -> left);
		}
		
		if ( root -> right != nullptr ){
			mirrorOfBinaryTree(root->right);
		}
		BinaryTreeNode * tmpNode = root -> left;
		root -> left = root -> right;
		root -> right = tmpNode;
	}
}


// 循环实现
void mirrorOfBinaryTreeLoop(BinaryTreeNode * root){
	if ( root == nullptr )
		return;
	stack<BinaryTreeNode *> s;
	s.push(root);
	while ( !s.empty() ){
		BinaryTreeNode * topNode = s.top();
		s.pop();
		// 交换节点
		BinaryTreeNode * tmpNode = topNode -> left;
		topNode -> left = topNode-> right;
		topNode->right = tmpNode;

		// 将topNode的孩子节点入栈
		if ( topNode->left != nullptr ){
			s.push(topNode->left);
		}
		if ( topNode->right != nullptr ){
			s.push(topNode->right);
		}
	}
}

void printTreeNode(BinaryTreeNode * root){
	if ( root != nullptr ){
		cout << root -> value << endl;
		printTreeNode(root->left);
		printTreeNode(root->right);
	}
}

int main(void){
	BinaryTreeNode* pNode8 = CreateBinaryTreeNode(8);
    BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6);
    BinaryTreeNode* pNode10 = CreateBinaryTreeNode(10);
    BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);
    BinaryTreeNode* pNode7 = CreateBinaryTreeNode(7);
    BinaryTreeNode* pNode9 = CreateBinaryTreeNode(9);
    BinaryTreeNode* pNode11 = CreateBinaryTreeNode(11);

	// Test 1
	ConnectTreeNodes(pNode8, pNode6, pNode10);
    ConnectTreeNodes(pNode6, pNode5, nullptr);
    ConnectTreeNodes(pNode10, nullptr, pNode11);

	// Test 2
    ConnectTreeNodes(pNode8, pNode6, nullptr);
    ConnectTreeNodes(pNode6, pNode5, nullptr);
    ConnectTreeNodes(pNode5, pNode9, nullptr);
	
	// Test 3
 	ConnectTreeNodes(pNode8, pNode6, pNode10);
    ConnectTreeNodes(pNode6, pNode5, pNode7);
    ConnectTreeNodes(pNode10, pNode9, pNode11);


	mirrorOfBinaryTree(pNode8);
	printTreeNode(pNode8);
	cout << "-----------" << endl;
	mirrorOfBinaryTreeLoop(nullptr);
	printTreeNode(nullptr);
	cout << "-----------" << endl;
	mirrorOfBinaryTreeLoop(pNode8);
	printTreeNode(pNode8);

	return 0;
}